package com.zjsru.plan2024.oneday;

import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;

/**
 * 1387. 将整数按权重排序
 *
 * @Author: cookLee
 * @Date: 2024-12-22
 */
public class GetKth {

    /**
     * 主
     * \
     * 如果 x 是偶数，那么 x = x / 2
     * 如果 x 是奇数，那么 x = 3 * x + 1
     * \
     * 输入：lo = 12, hi = 15, k = 2
     * 输出：13
     * 解释：12 的权重为 9（12 --> 6 --> 3 --> 10 --> 5 --> 16 --> 8 --> 4 --> 2 --> 1）
     * 13 的权重为 9
     * 14 的权重为 17
     * 15 的权重为 17
     * 区间内的数按权重排序以后的结果为 [12,13,14,15] 。对于 k = 2 ，答案是第二个整数也就是 13 。
     * 注意，12 和 13 有相同的权重，所以我们按照它们本身升序排序。14 和 15 同理。
     * \
     * 输入：lo = 7, hi = 11, k = 4
     * 输出：7
     * 解释：区间内整数 [7, 8, 9, 10, 11] 对应的权重为 [16, 3, 19, 6, 14] 。
     * 按权重排序后得到的结果为 [8, 10, 11, 7, 9] 。
     * 排序后数组中第 4 个数字为 7 。
     * \
     *
     * @param args args
     */
    public static void main(String[] args) {
        GetKth getKth = new GetKth();
        System.out.println(getKth.getKth(12, 15, 2));
    }

    public int getKth(int lo, int hi, int k) {
        List<Integer> count = new ArrayList<>();
        for (int i = lo; i <= hi; i++) {
            count.add(i);
        }
        count.sort(new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                if (GetKth.this.helper(o1) != GetKth.this.helper(o2)) {
                    return GetKth.this.helper(o1) - GetKth.this.helper(o2);
                } else {
                    return o1 - o2;
                }
            }
        });
        return count.get(k - 1);
    }

    private int helper(Integer number) {
        if (number == 1) {
            return 0;
        } else if ((number & 1) != 0) {
            //如果是奇数，+ 1 指 变为 1 所需的总操作步骤数。
            return this.helper(number * 3 + 1) + 1;
        } else {
            //如果是偶数，+ 1 指 变为 1 所需的总操作步骤数。
            return this.helper(number / 2) + 1;
        }
    }

}
